package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author Administrator
 * @date 2020/6/22 9:38
 */
public class PatternMatch {
    /**
     * 模式匹配
     * 你有两个字符串，即pattern和value。
     * pattern字符串由字母"a"和"b"组成，
     * 用于描述字符串中的模式。
     * 例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），
     * 该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。
     * 编写一个方法判断value字符串是否匹配pattern字符串。
     */
    @Test
    public void patternMatching() {
        Assert.assertTrue(patternMatching("abba", "dogcatcatdog"));
        Assert.assertFalse(patternMatching("abba", "dogcatcatfish"));
        Assert.assertFalse(patternMatching("aaaa", "dogcatcatdog"));
        Assert.assertTrue(patternMatching("abba", "dogdogdogdog"));
        Assert.assertTrue(patternMatching("bbba", "xxxxxxy"));
        Assert.assertTrue(patternMatching("aaaaab", "xahnxdxyaahnxdxyaahnxdxyaahnxdxyaauxuhuo"));
        Assert.assertTrue(patternMatching("bbbbbbbbbbbbbbabbbbb", "ppppppppppppppjsftcleifftfthiehjiheyqkhjfkyfckbtwbelfcgihlrfkrwireflijkjyppppg"));
    }

    public boolean patternMatching(String pattern, String value) {
        if (value.length() == 0 && (pattern.length() == 0 || pattern.length() == 1)) {
            return true;
        }
        if (pattern.length() == 0) {
            return false;
        }
        int[] a = new int[2], b = new int[2];
        int[][] patternI = new int[pattern.length()][2];
        patternI[0] = a;
        char ac = pattern.charAt(0);
        int count = 1, countB = 0, indexB = -1;
        for (int i = 1; i < pattern.length(); i++) {
            if (pattern.charAt(i) == ac) {
                patternI[i] = a;
                count++;
            } else {
                patternI[i] = b;
                countB++;
                indexB = indexB == -1 ? i : indexB;
            }
        }
        int endA = value.length() / count;
        a[1] = endA;
        if (countB == 0 && value.length() > (a[1] - a[0]) * count) {
            return false;
        }
        if (countB > 0) {
            b[0] = (a[1] - a[0]) * indexB;
            b[1] = b[0] + (value.length() - (a[1] - a[0]) * count) / countB;
        }
        while ((a[1] - a[0]) >= 0) {
            StringBuilder resV = new StringBuilder();
            for (int[] ins : patternI) {
                resV.append(value, ins[0], ins[1]);
            }
            if (resV.toString().equals(value) && !value.substring(a[0], a[1]).equals(value.substring(b[0], b[1]))) {
                return true;
            }
            if (countB == 0 || (a[1] - a[0]) == 0) {
                return false;
            }
            a[1]--;
            b[0] = (a[1] - a[0]) * indexB;
            b[1] = b[0] + (value.length() - (a[1] - a[0]) * count) / countB;
        }
        return false;
    }

    public boolean patternMatching2(String pattern, String value) {
        if (pattern.length() == 0) {
            return false;
        }
        int group = 1;
        String a = null, b = null;
        StringBuilder reg = new StringBuilder();
        for (int i = 0; i < pattern.length(); i++) {
            if (pattern.charAt(i) == 'a') {
                if (a != null) {
                    reg.append(a);
                } else {
                    reg.append("(\\w*)");
                    a = "\\" + group++;
                }
            } else {
                if (b != null) {
                    reg.append(b);
                } else {
                    reg.append("(\\w*)");
                    b = "\\" + group++;
                }
            }

        }
        Matcher matcher = Pattern.compile(reg.toString()).matcher(value);
        return matcher.matches();
    }

    public boolean patternMatching3(String pattern, String value) {
        int countA = 0, countB = 0;
        for (char ch : pattern.toCharArray()) {
            if (ch == 'a') {
                ++countA;
            } else {
                ++countB;
            }
        }
        if (countA < countB) {
            int temp = countA;
            countA = countB;
            countB = temp;
            char[] array = pattern.toCharArray();
            for (int i = 0; i < array.length; i++) {
                array[i] = array[i] == 'a' ? 'b' : 'a';
            }
            pattern = new String(array);
        }
        if (value.length() == 0) {
            return countB == 0;
        }
        if (pattern.length() == 0) {
            return false;
        }
        for (int lenA = 0; countA * lenA <= value.length(); ++lenA) {
            int rest = value.length() - countA * lenA;
            if ((countB == 0 && rest == 0) || (countB != 0 && rest % countB == 0)) {
                int lenB = (countB == 0 ? 0 : rest / countB);
                int pos = 0;
                boolean correct = true;
                String valueA = "", valueB = "";
                for (char ch : pattern.toCharArray()) {
                    if (ch == 'a') {
                        String sub = value.substring(pos, pos + lenA);
                        if (valueA.length() == 0) {
                            valueA = sub;
                        } else if (!valueA.equals(sub)) {
                            correct = false;
                            break;
                        }
                        pos += lenA;
                    } else {
                        String sub = value.substring(pos, pos + lenB);
                        if (valueB.length() == 0) {
                            valueB = sub;
                        } else if (!valueB.equals(sub)) {
                            correct = false;
                            break;
                        }
                        pos += lenB;
                    }
                }
                if (correct && !valueA.equals(valueB)) {
                    return true;
                }
            }
        }
        return false;
    }

}
